﻿#pragma once
#include<vector>
#include<iostream>
#include<string>
using namespace std;
namespace zyq
{
	template<size_t N>
	class bitset
	{
	public:
		bitset()
		{
			_bs.resize(N / 32 + 1);
		}

		void set(size_t pos)
		{
			size_t i = pos / 32;
			size_t j = pos % 32;

			_bs[i] |= (1 << j);
		}

		void reset(size_t pos)
		{
			size_t i = pos / 32;
			size_t j = pos % 32;

			_bs[i] & (!(1 << j));
		}

		bool test(size_t pos)
		{
			size_t i = pos / 32;
			size_t j = pos % 32;
			if (_bs[i] & (1 << j))
				return true;
			else
				return false;
		}
	private:
		std::vector<int> _bs;
	};


	struct HashFuncBKDR
	{
		/// @detail 本 算法由于在Brian Kernighan与Dennis Ritchie的《The CProgramming Language》
			// ⼀书被展⽰⽽得 名，是⼀种简单快捷的hash算法，也是Java⽬前采⽤的字符串的Hash算法累乘因⼦为31。
			size_t operator()(const string& s)
		{
			size_t hash = 0;
			for (auto ch : s)
			{
				hash *= 31;
				hash += ch;
			}
			return hash;
		}
	};
	struct HashFuncAP
	{
		// 由Arash Partow发明的⼀种hash算法。
		size_t operator()(const string& s)
		{
			size_t hash = 0;
			for (size_t i = 0; i < s.size(); i++)
			{
				if ((i & 1) == 0) // 偶数位字符
				{
					hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));
				}
				else // 奇数位字符
				{
					hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >>
						5)));
				}
			}
			return hash;
		}
	};
	struct HashFuncDJB
	{
			// 由Daniel J. Bernstein教授发明的⼀种hash算法。
			size_t operator()(const string & s)
		{
			size_t hash = 5381;
			for (auto ch : s)
			{
				hash = hash * 33 ^ ch;
			}
			return hash;
		}
	};
	template<size_t N,
		size_t X=5,
		class T=std::string,
		class HashFun1= HashFuncBKDR,
		class HashFunc2= HashFuncAP,
		class HashFunc3= HashFuncDJB>
	class BloomFilter
	{
	public:
		void set(const T& val)
		{
			size_t key1 = HashFun1()(val)%M;
			size_t key2 = HashFunc2()(val)%M;
			size_t key3 = HashFunc3()(val)%M;
			_bs.set(key1);
			_bs.set(key2);
			_bs.set(key3);
		}

		bool test(const T& val)
		{
			size_t key1 = HashFun1()(val) % M;
			size_t key2 = HashFunc2()(val) % M;
			size_t key3 = HashFunc3()(val) % M;

			if (_bs.test(key1) == false|| _bs.test(key2) == false|| _bs.test(key2) == false)
			{
				return false;
			}
			//这里存在误判，因为可能一个值本身不存在，但是别的值映射到他的位置了，导致误判
			//映射的位置都为0，一定不存在，但是都为1，也不一定存在
			return true;
		}
		// 获取公式计算出的误判率
		double getFalseProbability()
		{
			double p = pow((1.0 - pow(2.71, -3.0 / X)), 3.0);
			return p;
		}
	private:
		static const size_t M = N * X;
		bitset<M> _bs;
	};
	// 模拟位图找交集
	void test_bitset1()
	{
		int a1[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6 };
		int a2[] = { 5,3,5,99,6,99,33,66 };
		bitset<100> bs1;
		bitset<100> bs2;
		for (auto e : a1)
		{
			bs1.set(e);
		}
		for (auto e : a2)
		{
			bs2.set(e);
		}
		for (size_t i = 0; i < 100; i++)
		{
			if (bs1.test(i) && bs2.test(i))
			{
				cout << i << endl;
			}
		}
	}

	void TestBloomFilter1()
	{
		string strs[] = { "百度","字节","腾讯" };
		BloomFilter<10> bf;
		for (auto& s : strs)
		{
			bf.set(s);
		}
		for (auto& s : strs)
		{
			cout << bf.test(s) << endl;
		}
		for (auto& s : strs)
		{
			cout << bf.test(s + 'a') << endl;
		}
		cout << bf.test("摆渡") << endl;
		cout << bf.test("百渡") << endl;
	}

	void TestBloomFilter2()
	{
		srand(time(0));
		const size_t N = 10000000;
		BloomFilter<N> bf;
		//BloomFilter<N, 3> bf;
		//BloomFilter<N, 10> bf;
		std::vector<std::string> v1;
		std::string url = "https://www.cnblogs.com/-clq / archive / 2012 / 05 / 31 / 2528153.html";
			/*std::string url = "https://www.baidu.com/s?ie=utf-
			8 & f = 8 & rsv_bp = 1 & rsv_idx = 1 & tn = 65081411_1_oem_dg & wd = ln2 & fenlei = 256 & rsv_pq = 0x8d9962
			630072789f & rsv_t = ceda1rulSdBxDLjBdX4484KaopD % 2BzBFgV1uZn4271RV0PonRFJm0i5xAJ % 2F
			Do & rqlang = en & rsv_enter = 1 & rsv_dl = ib & rsv_sug3 = 3 & rsv_sug1 = 2 & rsv_sug7 = 100 & rsv_sug2 =
			0 & rsv_btype = i & inputT = 330 & rsv_sug4 = 2535";*/
			//std::string url = "猪⼋戒";
			for (size_t i = 0; i < N; ++i)
			{
				v1.push_back(url + std::to_string(i));
			}
		for (auto& str : v1)
		{
			bf.set(str);
		}
		// v2跟v1是相似字符串集（前缀⼀样），但是后缀不⼀样
		v1.clear();
		for (size_t i = 0; i < N; ++i)
		{
			std::string urlstr = url;
			urlstr += std::to_string(9999999 + i);
			v1.push_back(urlstr);
		}
		size_t n2 = 0;
		for (auto& str : v1)
		{
			if (bf.test(str)) // 误判
			{
				++n2;
			}
		}
		cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;
		// 不相似字符串集 前缀后缀都不⼀样
		v1.clear();
		for (size_t i = 0; i < N; ++i)
		{
			//string url = "zhihu.com";
			string url = "孙悟空";
			url += std::to_string(i + rand());
			v1.push_back(url);
		}
		size_t n3 = 0;
		for (auto& str : v1)
		{
			if (bf.test(str))
			{
				++n3;
			}
		}
		cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
		cout << "公式求出来的误判率：" << bf.getFalseProbability() << endl;
	}
};
